//
// Created by kqzhang on 2022/3/18.
//

#include "Model.h"

Model::Model(string &root) {
    this->file.setRoot(root);
}

void Model::initData() {
    initUser();
    initDemand();
    initDatOfSite();
    initQosConstraint();
}

void Model::initDatOfSite() {
    // getDataFromCsv
    vector<string> siteId;
    vector<vector<int>> qos;
    vector<int> siteBandWidth;

    file.getSiteId(siteId);
    file.getSiteBandWidth(siteBandWidth, siteId);
    file.getQos(qos);

    // assign id & bandwidth
    int length = siteId.size();
    allSite = vector<Site>(length);
    for (int i = 0; i < length; i++) {
        Site site(i, siteId[i]);
        site.setBandWidth(siteBandWidth[i]);
        site.setQos(qos[i]);
        allSite[i] = site;
    }
    this->n = length;
    
    // initNormalizeQos(qos);
}

void Model::initQosConstraint() {
    // get data from csv and assign
    this->qosConstraint = file.getQosConstraint();
}

void Model::initUser() {
    // get data from csv
    file.getUserId(this->user);
    this->m = this->user.size();
}

void Model::initDemand() {
    // get data from csv
    file.getDemand(this->demand, this->user);
}

void Model::initNormalizeQos(vector<vector<int>> &qos) {
    for (int i = 0; i < qos[0].size(); i++) {
        double count = 0;
        vector<double> userQos(qos.size(), 0);
        for (int j = 0; j < qos.size(); j++) {
            count += qos[j][i];
        }
        for (int j = 0; j < qos.size(); j++) {
            userQos[j] = qos[j][i] / count;
        }
        normalizeQos.push_back(userQos);
    }
}

void Model::GA() {
    this->oldDistribute = vector<vector<int>>(this->n);
    for (int i = 0; i < demand.size(); i++) {
        this->currentDemand = demand[i];
        if (i < 20) {
            Individual meanIndividual;
            getMeanIndividual(meanIndividual);
            bestIndividual.push_back(meanIndividual);
            updateOldDistribute(meanIndividual.getIndividual());
        } else {
            initGroup();
            for (int j = 0; j < this->generationTime; j++) {
                crossover();
                mutation();
                select();
            }
            bestIndividual.push_back(this->individual[0]);
            updateOldDistribute(this->individual[0].getIndividual());

            cout << "ans is " << this->individual[0].getFitness() << endl;
        }

        this->individual.clear();
    }

    printResult();
}

void Model::getMeanIndividual(Individual &individual) {
    vector<vector<int>> distribute;

    for (int i = 0; i < this->m; i++) {
        int allBand = this->currentDemand[i], num = 0;
        vector<int> disOfUser(this->n, 0);
        for (int j = 0; j < this->n; j++) {
            if (allSite[j].getQos(i) >= this->qosConstraint) {
                disOfUser[j] = -1;
            } else {
                num++;
            }
        }
        int meanValue = allBand / num, remainder = allBand % num, remainderFlag = 0;
        for (int j = 0; j < this->n; j++) {
            if (disOfUser[j] != -1) {
                if (remainderFlag ==0 && meanValue + remainder < allSite[j].getBandWidth()) {
                    disOfUser[j] = meanValue + remainder;
                    remainderFlag = 1;
                } else {
                    disOfUser[j] = meanValue;
                }
            }
        }
        distribute.push_back(disOfUser);
    }
    individual.setIndividual(distribute);
    if (!checkBand(distribute))
        cout << "mean error" << endl;
    individual.setFitness(0);
}

void Model::updateOldDistribute(vector<vector<int>> &distribute) {
    vector<int> dis(this->n, 0);
    for (int i = 0; i < this->n; i++) {
        for (int j = 0; j < this->m; j++) {
            int value = distribute[j][i];
            if (value > 0)
                dis[i] = dis[i] + value;
        }
    }

    for (int i = 0; i < this->n; i++) {
        this->oldDistribute[i].push_back(dis[i]);
    }
}

void Model::initGroup() {
    int i = 0;
    while (i < this->groupSize) {
        Individual singleIndividual;
        vector<vector<int>> distribute;

        for (int j = 0; j < this->m; j++) {
            int allBand = this->currentDemand[j], num = 0;
            vector<int> disOfUser(this->n, 0);
            for (int z = 0; z < this->n; z++) {
                if (allSite[z].getQos(j) >= this->qosConstraint) {
                    disOfUser[z] = -1;
                } else {
                    num++;
                }
            }
            getRandomValue(num, allBand, disOfUser);
            distribute.push_back(disOfUser);
        }
        singleIndividual.setIndividual(distribute);
        if (check(singleIndividual)) {
            i++;
            getFitness(singleIndividual);
            this->individual.push_back(singleIndividual);
        }
    }
}

void Model::crossover() {
    Individual one, two;

    int i = 0;
    while (i < 2 * this->groupSize) {
        int positionOne = (int)(groupSize * random_0_1());
        int positionTwo = (int)(groupSize * random_0_1());

        while (positionOne == groupSize)
            positionOne = (int)(groupSize * random_0_1());
        while (positionOne == positionTwo || positionTwo == groupSize) {
            positionTwo = (int)(groupSize * random_0_1());
        }
        one = this->individual[positionOne];
        two = this->individual[positionTwo];

        crossTwoIndividual(one, two);

        if (check(one) && checkBand(one.getIndividual())) {
            getFitness(one);
            this->individual.push_back(one);
        }
        i++;
    }
}

void Model::mutation() {
    for (int i = 0; i < this->individual.size(); i++) {
        double random_m = random_0_1();
        if (random_m > pm) {
            continue;
        }
        Individual individual = this->individual[i];
        auto distribute = individual.getIndividual();

        // random user
        int positionUser = (int)(this->m * random_0_1());
        while (positionUser == this->m)
            positionUser = (int)(this->m * random_0_1());

        // random site
        int positionLeft = (int)(this->n * random_0_1());
        int positionRight = (int)(this->n * random_0_1());
        while (positionLeft == this->n || distribute[positionUser][positionLeft] == -1)
            positionLeft = (int)(this->n * random_0_1());
        while (positionLeft == positionRight || positionRight == this->n || distribute[positionUser][positionRight] == -1)
            positionRight = (int)(this->n * random_0_1());

        swap(distribute[positionUser][positionLeft], distribute[positionUser][positionRight]);
        individual.setIndividual(distribute);
        getFitness(individual);
        this->individual.push_back(individual);
    }
}

void Model::select() {
    vector<Individual> selectIndividual;
    sort(this->individual.begin(), this->individual.end(), cmp);

    // elitism select top 5
    for (int i = 0 ; i < 5; i++) {
        selectIndividual.push_back(this->individual[i]);
    }

    // tournament select
    int size = this->individual.size();
    for (int i = 0; i < this->groupSize - 5; i++) {
        int one = (int)(size * random_0_1());
        int two = (int)(size * random_0_1());
        while (one == size)
            one = (int)(size * random_0_1());
        while (one == two || two == size)
            two = (int)(size * random_0_1());

        selectIndividual.push_back(one < two ? this->individual[one] : this->individual[two]);
    }

    this->individual.clear();
    this->individual = selectIndividual;
}

void Model::getFitness(Individual &individual) {
    auto distribute = individual.getIndividual();
    vector<int> dis(this->n, 0);

    for (int i = 0; i < this->n; i++) {
        for (int j = 0; j < this->m; j++) {
            if (distribute[j][i] > 0)
                dis[i] += distribute[j][i];
        }
    }

    int value = 0;
    for (int i = 0; i < this->n; i++) {
        auto oldDis = oldDistribute[i];
        oldDis.push_back(dis[i]);
        int length = oldDis.size();
        sort(oldDis.begin(), oldDis.end());

        int position = (int)(length * 0.95);
        value += oldDis[position];
    }

    individual.setFitness(value);
}

int Model::getFitness() {
    int value = 0;
    for (int i = 0; i < this->n; i++) {
        auto &oldDis = oldDistribute[i];
        int length = oldDis.size();
        sort(oldDis.begin(), oldDis.end());

        int position = (int)(length * 0.95);
        value += oldDis[position];
    }

    return value;
}

void Model::getRandomValue(int num, int allBand, vector<int> &disOfUser) {
    vector<int> random(num - 1, 0), value(num, 0);
    for (int i = 0; i < num - 1; i++) {
        random[i] = (int)(allBand * random_0_1());
    }

    sort(random.begin(), random.end());
    for (int i = 0; i < random.size(); i++) {
        int randomValue = 0;
        if (i == 0)
            randomValue = random[i];
        else
            randomValue = random[i] - random[i - 1];
        value[i] = randomValue;
    }
    value[num - 1] = allBand - random[num - 2];

    // test
    int count = 0;
    for (int i = 0; i < num; i++)
        count += value[i];

    if (count != allBand)
        cout << "error" << endl;

    int j = 0;
    for (int i = 0; i < this->n; i++) {
        if (disOfUser[i] != -1) {
            disOfUser[i] = value[j];
            j++;
        }
    }
}

bool Model::check(Individual &individual) {
    vector<int> useBand(this->n, 0);
    auto distribute = individual.getIndividual();

    // 分配带宽不超过最大带宽
    for (int i = 0; i < this->m; i++) {
        for (int j = 0; j < this->n; j++ ) {
            useBand[j] += distribute[i][j];
        }
    }
    for (int i = 0; i < this->n; i++) {
        if (useBand[i] > allSite[i].getBandWidth())
            return false;
    }

    // 用户分配方案是否合理
    for (int i = 0; i < this->m; i++) {
        int count = 0;
        for (int j = 0; j < this->n; j++) {
            if (distribute[i][j] != -1) {
                count += distribute[i][j];
            }
        }
        if (count != currentDemand[i]) {
            cout << "i is " << i << "current is " << count << "real is " << currentDemand[i] << endl;
            return false;
        }
    }

    return true;
}

void Model::crossTwoIndividual(Individual &parentOne, Individual &parentTwo) {
    auto one = parentOne.getIndividual();
    auto two = parentTwo.getIndividual();
    for (int i = 0; i < this->m; i++) {
        int count = 0, before = sum(one[i]);
        for (int j = 0; j < this->n; j++) {
            int sum = one[i][j] + two[i][j];
            int mean = sum / 2;

            if (mean != -1) {
                one[i][j] = mean;
                count += mean;
            }
        }
        for (int j = 0; j < this->n; j++) {
            if (one[i][j] != -1) {
                one[i][j] += (before - count);
                break;
            }
        }

        int now = sum(one[i]);
        if (now != before) {
            cout << "now is " << now << "before is " << before  << endl;
        }
    }
    parentOne.setIndividual(one);
}

void Model::printResult() {
    string outputPath = file.getRoot() + "output/solution.txt";

    ofstream outputFile;
    outputFile.open(outputPath);

    int length = this->demand.size();
    if (outputFile.is_open()) {
        for (int i = 0; i < length; i++) {
            auto individual = bestIndividual[i];
            auto distribute = individual.getIndividual();
            for (int j = 0; j < this->m; j++) {
                if (demand[i][j] == 0) {
                    outputFile << this->user[j] << ":" << endl;
                    continue;
                }
                outputFile << this->user[j] << ":";
                int flag = 0;
                for (int z = 0; z < this->n; z++) {
                    if (distribute[j][z] != -1 && distribute[j][z] != 0) {
                        if (flag != 0) {
                            outputFile << ",";
                        }
                        flag = 1;
                        outputFile << "<" << allSite[z].getName() << "," << distribute[j][z] << ">";
                    }
                }
                outputFile << endl;
            }
        }
    } else {
        cout << "output open error" << endl;
    }

    outputFile.close();
}

int Model::sum(Individual &test) {
    int count = 0;
    for (int i = 0; i < this->m; i++) {
        for (int j = 0; j < this->n; j++) {
            count += test.getIndividual()[i][j];
        }
    }

    return count;
}

int Model::sum(vector<int> &test) {
    int count = 0;
    for (int i = 0; i < test.size(); i++) {
            count += test[i];
    }

    return count;
}

double Model::sum(vector<double> &test) {
    double count = 0;
    for (int i = 0; i < test.size(); i++) {
        if (test[i] != -1)
            count += test[i];
    }

    return count;
}

void Model::test() {
    int demandSize = this->demand.size();
    this->bestIndividual = vector<Individual>(demandSize);
    this->oldDistribute = vector<vector<int>>(this->n);
    for (int i = 0; i < demandSize; i++) {
        this->currentDemand = demand[i];
        int _l = 0;
        while (_l < 1) {
            Individual singleIndividual;
            vector<vector<int>> distribute;

            for (int j = 0; j < this->m; j++) {
                int allBand = this->currentDemand[j], num = 0;
                vector<int> disOfUser(this->n, 0);
                for (int z = 0; z < this->n; z++) {   
		            if (allSite[z].getQos(j) >= this->qosConstraint) {
	    	            disOfUser[z] = -1;
                    } else {
                        num++;
                    }
                }
                getRandomValue(num, allBand, disOfUser);
		        distribute.push_back(disOfUser);
            }
            singleIndividual.setIndividual(distribute);
            if (check(singleIndividual) && checkBand(singleIndividual.getIndividual())) {
                _l++;
                updateOldDistribute(distribute);
                getFitness(singleIndividual);
                this->bestIndividual[i] = singleIndividual;
           }
        }
    }
    printResult();
}

bool Model::checkBand(vector<vector<int>> &distribute) {
    for (int i = 0; i < this->m; i++) {
        int count = 0;
        for (int j = 0; j < this->n; j++) {
            if (distribute[i][j] != -1)
                count += distribute[i][j];
        }

        if (count != this->currentDemand[i]) {
            cout << i << " "<< count << " " << this->currentDemand[i] << endl;
            return false;
        }
    }

    return true;
}

void Model::assignOne() {
    this->oldDistribute = vector<vector<int>>(this->n);
    this->midValue = vector<int>(this->n, 0);

    for (int i = 0; i < demand.size(); i++) {
        this->currentDemand = demand[i];

        Individual thisIndividual;
        vector<vector<int>> distribute(this->m, vector<int>(this->n));
        createIndividual(distribute);
        thisIndividual.setIndividual(distribute);
        bestIndividual.push_back(thisIndividual);
        updateOldDistribute(distribute);
        updateMidValue(i);

        check(thisIndividual);

        for (auto &i: allSite)
            i.updateLeftBand();
    }

    printResult();
}

void Model::createIndividual(vector<vector<int>> &distribute) {
    vector<vector<int>> connectSite(this->m);
    vector<int> connectUser(this->n, 0);
    for (int i = 0; i < this->m; i++) {
        for (int j = 0; j < this->n; j++) {
            if (this->allSite[j].getQos(i) >= this->qosConstraint) {
                distribute[i][j] = -1;
            } else {
                connectSite[i].push_back(j);
                connectUser[j]++;
                distribute[i][j] = midValue[j];
            }
        }
    }

    for (int i = 0; i < this->m; i++) {
        for (int j = 0; j < this->n; j++) {
            if (distribute[i][j] != -1) {
                distribute[i][j] = distribute[i][j] / connectUser[j];
            }
        }
    }

    getAssignValue(distribute, connectSite);
}

void Model::getAssignValue(vector<vector<int>> &distribute, vector<vector<int>> &connectSite) {
    priority_queue<PII, vector<PII>> userDemandPq;

    for (int i = 0; i < this->currentDemand.size(); i++) {
        userDemandPq.emplace(currentDemand[i], i);
    }

    while (!userDemandPq.empty()) {
        auto [userDemand, userId] = userDemandPq.top();
        userDemandPq.pop();

        priority_queue<PII, vector<PII>> pq;
        vector<int> &singleDistribute = distribute[userId];
        if (connectSite[userId].empty())
            continue;
        int num = connectSite[userId].size(), sum = 0;
        for (int j = 0; j < this->n; j++) {
            if (singleDistribute[j] != -1)
                sum += singleDistribute[j];
        }

        // init pq
        for (int j = 0; j < num; j++) {
            int leftBand = this->allSite[connectSite[userId][j]].getLeftWidth();
            pq.emplace(leftBand, connectSite[userId][j]);
        }

        // get mean value
        int all = userDemand - sum;
        vector<int> meanNValue(num, 0);
        if (all < 0) {
            for (int j = 0; j < num; j++) {
//                meanNValue[j] = midValue[connectSite[userId][j]];
                meanNValue[j] = distribute[userId][connectSite[userId][j]];
            }
        }
        meanValue(meanNValue, all, num);
        auto test = distribute;

        if (all < 0) {
            int remainder = 0;
            for (int j = 0; j < num; j++) {
                int id = connectSite[userId][j];
                int leftBand = allSite[id].getLeftWidth();

                int demo = distribute[userId][id] + meanNValue[j] + remainder;
                if (demo <= leftBand && demo >= 0) {
                    distribute[userId][id] += (meanNValue[j] + remainder);
                    remainder = 0;
                } else if (demo > leftBand){
                    remainder = demo - leftBand;
                    distribute[userId][id] = leftBand;
                } else {
                    remainder = demo;
                    distribute[userId][id] = 0;
                }
                this->allSite[id].changeLeftWidth(distribute[userId][id]);
            }

            if (remainder != 0)
                cout << "remainder " << remainder << " ooo" << endl;
            continue;
        }

        int remainder = 0, j = 0;
        while (!pq.empty()) {
            auto [leftBand, id] = pq.top();
            pq.pop();

            int demo = distribute[userId][id] + meanNValue[j] + remainder;
            if (demo <= leftBand && demo >= 0) {
                distribute[userId][id] += (meanNValue[j] + remainder);
                remainder = 0;
            } else if (demo > leftBand){
                remainder = demo - leftBand;
                distribute[userId][id] = leftBand;
            } else {
                remainder = demo;
                distribute[userId][id] = 0;
            }
            this->allSite[id].changeLeftWidth(distribute[userId][id]);
            j++;
        }

        if (remainder != 0) {
            // init pq
            for (auto j : connectSite[userId]) {
                int leftBand = this->allSite[j].getLeftWidth();
                pq.emplace(leftBand, j);
            }

            while (!pq.empty() && remainder != 0) {
                auto [leftBand, id] = pq.top();
                pq.pop();

                if (remainder <= leftBand) {
                    distribute[userId][id] += remainder;
                    this->allSite[id].changeLeftWidth(remainder);
                    remainder = 0;
                } else {
                    distribute[userId][id] += leftBand;
                    this->allSite[id].changeLeftWidth(leftBand);
                    remainder -= leftBand;
                }
            }
        }
    }
}

void Model::meanValue(vector<int> &meanNValue, int all, int num) {
    if (all > 0) {
        /**
         * one
         */
        int mean = all / num, remainder = all % num;

        for (int i = 0; i < meanNValue.size(); i++) {
            if (i == 0)
                meanNValue[i] = mean + remainder;
            else
                meanNValue[i] = mean;
        }

        sort(meanNValue.begin(), meanNValue.end(), greater<int>());

//        vector<int> random(num - 1, 0);
//        for (int i = 0; i < num - 1; i++) {
//            random[i] = (int)(all * random_0_1());
//        }
//
//        sort(random.begin(), random.end());
//        for (int i = 0; i < random.size(); i++) {
//            int randomValue = 0;
//            if (i == 0)
//                randomValue = random[i];
//            else
//                randomValue = random[i] - random[i - 1];
//            meanNValue[i] = randomValue;
//        }
//        meanNValue[num - 1] = all - random[num - 2];
//
//        if (sum(meanNValue) != all)
//            cout << "+ error" << endl;

    } else {
        vector<double> normalize(num, 0);
        for (int i = 0; i < num; i++) {
            normalize[i] = (double)meanNValue[i] / sum(meanNValue);
        }

        int count = 0;
        for (int i = 0; i < num; i++) {
            meanNValue[i] = (int)(all * normalize[i]);
            count += meanNValue[i];
        }

        vector<int> test = meanNValue;
        meanNValue[0] += (all - count);

        count = 0;
        for (int i = 0; i < num; i++) {
            count += meanNValue[i];
        }

        if (count != all) {
            cout << "normalize is " << sum(normalize)<< endl;
            cout << "- error " << "current " << sum(meanNValue) << "real " << all << "num is " << n << endl;
        }
    }
}

void Model::updateMidValue(int T) {
    /**
     * one
     */
    for (int i = 0; i < this->n; i++) {
        sort(oldDistribute[i].begin(), oldDistribute[i].end());
    }
    int length = oldDistribute[0].size();
    for (int i = 0; i < this->n; i++) {
        if (oldDistribute[i].empty()) {
            midValue[i] = 0;
            continue;
        }
        midValue[i] = this->oldDistribute[i][(int)((1.0 - this->meanPercentage / 2) * length)];
    }

    /**
     * two
     */
//    auto dis = bestIndividual[bestIndividual.size() - 1].getIndividual();
//    for (int i = 0; i < this->m; i++) {
//        for (int j = 0; j < this->n; j++) {
//            if (dis[i][j] != -1) {
//                midValue[j] = min(midValue[j] , dis[i][j]);
//            }
//        }
//    }

    /**
     * three
     */
//     int count = sum(this->currentDemand);
//     for (int i = 0; i < this->n; i++) {
//         midValue[i] = min(midValue[i], count / this->n);
//     }

    /**
     * four
     */
//    vector<double> normalize(this->n, 0);
//    for (int i = 0; i < this->m; i++) {
//        for (int j = 0; j < this->n; j++) {
//            if (isConnect[T][i][j])
//                normalize[j]++;
//        }
//    }
////    for (int i = 0; i < this->n; i++) {
////        normalize[i] = abs(log(normalize[i]));
////    }
//    int demandCount = sum(currentDemand);
//    int count = sum(normalize);
//    for (int i = 0; i < this->n; i++) {
//        normalize[i] = normalize[i] / count;
//        midValue[i] = normalize[i] * demandCount;
//    }
}

void Model::assignTwo() {
    this->oldDistribute = vector<vector<int>>(this->n);
    this->midValue = vector<int>(this->n, 0);
    vector<int> connectSite(this->m, 0);
    vector<int> connectUser(this->n, 0);
    vector<vector<int>> connectSiteId(this->m);

    for (int i = 0; i < this->m; i++) {
        for (int j = 0; j < this->n; j++) {
            if (this->allSite[j].getQos(i) < this->qosConstraint) {
                connectSite[i]++;
                connectUser[j]++;
                connectSiteId[i].push_back(j);
            }
        }
    }
    vector<double> normalize(this->n, 0);
    for (int i = 0; i < this->n; i++) {
        normalize[i] = log(connectUser[i]);
    }

    double count = sum(normalize);
    for (int i = 0; i < this->n; i++) {
        normalize[i] = normalize[i] / count;
    }

    connectSiteNor = vector<vector<double>>(this->m);
    for (int i = 0; i < this->m; i++) {
        connectSiteNor[i] = vector<double>(connectSiteId[i].size(), 0);
        for (int j = 0; j < connectSiteId[i].size(); j++) {
            connectSiteNor[i][j] = normalize[connectSiteId[i][j]];
        }
        double thisCount = sum(connectSiteNor[i]);
        for (int j = 0; j < connectSiteId[i].size(); j++) {
            connectSiteNor[i][j] = connectSiteNor[i][j] / thisCount;
        }
    }

    for (int i = 0; i < demand.size(); i++) {
        this->currentDemand = demand[i];

        Individual thisIndividual;
        vector<vector<int>> distribute(this->m, vector<int>(this->n));
        createIndividual(distribute);
        thisIndividual.setIndividual(distribute);
        bestIndividual.push_back(thisIndividual);
        updateOldDistribute(distribute);
        updateMidValue(i);

        check(thisIndividual);

        for (auto &i: allSite)
            i.updateLeftBand();
    }

    printResult();
}

void Model::assignThree() {
    int demandSize = this->demand.size();

    // init data
    userConnectSite = vector<int>(this->m, 0);
    siteConnectUser = vector<vector<int>>(this->n);
    isConnect = vector<vector<vector<bool>>>(demandSize, vector<vector<bool>>(this->m, vector<bool>(this->n, false)));
    preLeftBand = vector<vector<int>>(demandSize, vector<int>(this->n));

    // init leftBand
    for (int i = 0; i < demandSize; i++) {
        for (int j = 0; j < this->n; j++)
            preLeftBand[i][j] = allSite[j].getBandWidth();
    }

    // init connect graph
    auto singleConnect = vector<vector<bool>>(this->m, vector<bool>(this->n, false));
    for (int i = 0; i < this->m; i++) {
        for (int j = 0; j < this->n; j++) {
            if (allSite[j].getQos(i) < this->qosConstraint) {
                singleConnect[i][j] = true;
                siteConnectUser[j].push_back(i);
                userConnectSite[i]++;
            }
        }
    }
    for (int i = 0; i < demandSize; i++)
        isConnect[i] = singleConnect;

    // bandWidth pq
    for (int i = 0; i < this->n; i++) {
        bandSitePq.emplace(allSite[i].getBandWidth(), i);
    }

    // get top 5% assign
    getTop5Assign();
//    getTop5Assign();

    // init expectTimeDemand
    int count = 0;
    for (int i = 0; i < demandSize; i++) {
        for (int j = 0; j < this->m; j++) {
            count += demand[i][j];
        }
    }
    this->expectTimeDemand = count / demandSize;

    // assign left time
    assign();

    for (int i = 0; i < top5Assign.size(); i++) {
        auto assign = top5Assign[i];
        auto &dis = bestIndividual[assign.time].getIndividual();
        dis[assign.user][assign.site] += assign.assignBand;
    }

    this->demand.clear();
    initDemand();

    printResult();
}

void Model::getTop5Assign() {
    int demandSize = this->demand.size();
    int length = (1.0 - this->meanPercentage) * demandSize;

    while (!bandSitePq.empty()) {
        vector<vector<vector<int>>> siteCon(demandSize, vector<vector<int>>(this->n));
        vector<vector<int>> userCon(demandSize, vector<int>(this->m, 0));

        auto [bandWidth, siteId] = bandSitePq.top();
        bandSitePq.pop();

        // init con
        for (int i = 0; i < demandSize; i++) {
            for (int j = 0; j < this->m; j++) {
                for (int k = 0; k < this->n; k++) {
                    if (isConnect[i][j][k]) {
                        siteCon[i][k].push_back(j);
                        userCon[i][j]++;
                    }
                }
            }
        }

        priority_queue<PII, vector<PII>> demandPq;

        for (int j = 0; j < demandSize; j++) {
            int count = 0;
            for (int z = 0; z < siteCon[j][siteId].size(); z++)
                count += demand[j][siteCon[j][siteId][z]];

            demandPq.emplace(count, j);
        }

        for (int i = 0; i < length; i++) {
            auto [sumDemand, T] = demandPq.top();
            demandPq.pop();

            int perBandWidth = bandWidth;
            if (sumDemand <= perBandWidth) {
                if (perBandWidth == 0)
                    continue;
                for (auto j : siteCon[T][siteId]) {
                    struct preAssign assign;
                    assign.time = T;
                    assign.site = siteId;
                    assign.user = j;
                    assign.assignBand = demand[T][j];

                    preLeftBand[T][siteId] -= demand[T][j];
                    top5Assign.push_back(assign);
                    demand[T][j] = 0;
                    isConnect[T][j][siteId] = false;
                }
            } else if (sumDemand > perBandWidth) {
                if (perBandWidth == 0)
                    continue;
                // need update
                priority_queue<PII, vector<PII>, greater<PII> > pq;
                for (auto j : siteCon[T][siteId]) {
                    pq.emplace(userCon[T][j], j);
                }

                while (!pq.empty()) {
                    auto [num, j] = pq.top();
                    pq.pop();
                    if (perBandWidth == 0) {
                        isConnect[T][j][siteId] = false;
                        continue;
                    }
                    int band = min(perBandWidth, demand[T][j]);

                    struct preAssign assign;
                    assign.time = T;
                    assign.site = siteId;
                    assign.user = j;
                    assign.assignBand = band;

                    preLeftBand[T][siteId] -= band;
                    top5Assign.push_back(assign);
                    demand[T][j] -= band;
                    perBandWidth -= band;
                    isConnect[T][j][siteId] = false;
                }
            }
        }
    }
}

void Model::assign() {
    // init data
    int demandSize = this->demand.size();
    this->oldDistribute = vector<vector<int>>(this->n);
    this->midValue = vector<int>(this->n, 0);

    for (int i = 0; i < demandSize; i++) {
        this->currentDemand = demand[i];
        for (int j = 0; j < this->n; j++)
            allSite[j].setLeftWidth(preLeftBand[i][j]);

        Individual thisIndividual;
        vector<vector<int>> distribute(this->m, vector<int>(this->n, 0));
//        singleAssign(distribute, i);
//        avgAssign(distribute, i);
        proportionAssign(distribute, i);
        thisIndividual.setIndividual(distribute);
        bestIndividual.push_back(thisIndividual);
        //updateOldDistribute(distribute);
        //updateMidValue(i);

        check(thisIndividual);
    }
}

void Model::singleAssign(vector<vector<int>> &distribute, int T) {
    vector<vector<int>> connectSite(this->m);
    for (int i = 0; i < this->m; i++) {
        for (int j = 0; j < this->n; j++) {
            if (isConnect[T][i][j]) {
                distribute[i][j] = midValue[j] / siteConnectUser[j].size();
                connectSite[i].push_back(j);
            }
        }
    }

    getAssignValue(distribute, connectSite);
}

void Model::avgAssign(vector<vector<int>> &distribute, int T) {
    vector<vector<int>> connectSite(this->m);
    for (int i = 0; i < this->m; i++) {
        for (int j = 0; j < this->n; j++) {
            if (isConnect[T][i][j]) {
                connectSite[i].push_back(j);
            }
        }
    }

    for (int i = 0; i < this->m; i++) {
        int connectNum = connectSite[i].size();
        int thisDemand = currentDemand[i];

        if (thisDemand == 0) continue;

        int mean = thisDemand / connectNum, remainder = thisDemand % connectNum;
        for (auto j : connectSite[i]) {
            if (mean + remainder <= allSite[j].getLeftWidth()) {
                distribute[i][j] = mean + remainder;
                remainder = 0;
            } else {
                distribute[i][j] = allSite[j].getLeftWidth();
                remainder = mean + remainder - allSite[j].getLeftWidth();
            }
            allSite[j].changeLeftWidth(distribute[i][j]);
        }

        if (remainder != 0)
            cout << "there is still remainder not assign" << endl;
    }
}

void Model::proportionAssign(vector<vector<int>> &distribute, int T) {
    vector<vector<int>> connectSite(this->m);
    for (int i = 0; i < this->m; i++) {
        for (int j = 0; j < this->n; j++) {
            if (isConnect[T][i][j]) {
                connectSite[i].push_back(j);
            }
        }
    }

    for (int i = 0; i < this->m; i++) {
        int connectNum = connectSite[i].size();
        int thisDemand = currentDemand[i];

        if (thisDemand == 0) continue;

        vector<double> proportionLeftBand(connectNum, 0);
        for (int j = 0; j < connectNum; j++) {
            proportionLeftBand[j] = allSite[connectSite[i][j]].getLeftWidth();
        }
        int allCount = sum(proportionLeftBand);
        for (int j = 0; j < connectNum; j++) {
            proportionLeftBand[j] = proportionLeftBand[j] / allCount;
        }
        vector<int> assignValue(connectNum, 0);
        int count = 0;
        for (int j = 0; j < connectNum; j++) {
            assignValue[j] = (int)(proportionLeftBand[j] * thisDemand);
            count += assignValue[j];
        }
        assignValue[0] += (thisDemand - count);

        int remainder = 0;
        for (int j = 0; j < connectNum; j++) {
            int site = connectSite[i][j];
            int leftBand = allSite[site].getLeftWidth();

            if (assignValue[j] + remainder <= leftBand) {
                distribute[i][site] = assignValue[j] + remainder;
                remainder = 0;
            } else {
                distribute[i][site] = leftBand;
                remainder = assignValue[j] + remainder - leftBand;
            }
            allSite[site].changeLeftWidth(distribute[i][site]);
        }

        if (remainder != 0)
            cout << "there is still remainder not assign" << endl;
    }
}